//
// Description: 98. 验证二叉搜索树
// Created by Loading on 2022/2/25.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

bool isValidBST(TreeNode *root) {
    // 维护一个极大值和极小值
    function<bool(TreeNode *, long long, long long)> check = [&](TreeNode *node, long long lower, long long upper) {
        if (!node) {
            return true;
        }
        if (node->val >= upper || node->val <= lower) {
            return false;
        }

        // 判断左子树时，极大值变为当前节点；判断右子树时，极小值变为当前节点
        return check(node->left, lower, node->val) && check(node->right, node->val, upper);
    };

    return check(root, LONG_LONG_MIN, LONG_LONG_MAX);
}

int main() {
    vector<int> nums = {5, 4, 6, -1, -1, 3, 7};
    auto root = generateTreeNode(nums);
    bool res = isValidBST(root);
    cout << res << endl;

    return 0;
}